package seach

func merge(li []int, low, mid, high int) {
	i := low
	j := mid + 1
	tmpLi := make([]int, len(li))
	c:=0
	for i <= mid && j <= high {
		if li[i] < li[j] {
			tmpLi[c]= li[i]
			i++
		} else {
			tmpLi[c] = li[j]
			j++
		}
		c++
	}
	if i <= mid {
		tmpLi = append(tmpLi[0:c], li[i:mid+1]...)
	}
	if j <= high {
		tmpLi = append(tmpLi[0:c], li[j:high+1]...)
	}
	//fmt.Println(li)
	//fmt.Println(tmpLi)
	li=append(li[0:low],tmpLi...)
	//for i := 0; i < len(tmpLi); i++ {
	//	li[low+i] = tmpLi[i]
	//}

}

func mergeSort(li []int, low, high int) {
	if low < high {
		mid := (high + low) / 2
		mergeSort(li, low, mid)
		mergeSort(li, mid+1, high)
		merge(li, low, mid, high)
	}

}
